package Hot100.Medium.GreedyAndDP.DynamicPlanning.CompleteBag;

public class LC322_MoneyForExchange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
    }

    public int coinChange(int[] coins, int amount){
        int n = coins.length;
        int max = Integer.MAX_VALUE / 2;
        // 确定dp数组的含义，dp[i][j]表示背包容量为j时，从前i种硬币里选择，有多少种方法组成容量j
        int[][] dp = new int[n + 1][amount + 1];
        // 初始化dp数组
        // 第一行也就是0种硬币，没有办法凑成金额j，因此设置为max
        for(int i = 1; i <= amount; i++){
            dp[0][i] = max;
        }
        // 第一列，背包容量j为0，需要0个硬币凑成amount，因此设置为0
        for(int j = 0; j <= n; j++){
            dp[j][0] = 0;
        }

        // 下面考虑递推公式，对于完全背包，dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
        // 对于本题要考虑dp的意义以及相较于完全背包的变化，题目中问最少的硬币个数的组合，因此要用min来选择，此外，value[i]也不再是硬币的值，而是1，因为数组表示的是有多少种放法，而不是让求值
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= amount; j++){
                if(coins[i - 1] > j){ // 当前硬币比背包容量大，因此放不下，选上面一行也就是不选该硬币时dp的数组
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                }
            }
        }
        return dp[n][amount] >= max ? -1 : dp[n][amount];
    }

}
